import functools

MOD = 10 ** 9 + 7


class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        self.left = s1
        self.right = s2
        self.evil = evil
        self.evil_kmp = self.count_kmp(evil)
        self.size1, self.size2 = len(s1), len(evil)
        return self.dfs(0, 0, True, True)

    @functools.lru_cache(None)
    def dfs(self, idx, match, lower, higher):
        """idx=当前匹配位置,match=当前匹配evil的长度"""
        if match == self.size2:  # 匹配evil
            return 0
        if idx == self.size1:  # 搜索到结尾
            return 1

        ans = 0

        left_ch = self.left[idx] if lower else "a"
        right_ch = self.right[idx] if higher else "z"

        for a in range(ord(left_ch), ord(right_ch) + 1):
            ch = chr(a)

            # KMP求匹配长度
            l = match
            while l != -1 and self.evil[l] != ch:
                l = self.evil_kmp[l]

            ans += self.dfs(idx + 1, l + 1, lower and ch == left_ch, higher and ch == right_ch)
            ans %= MOD

        return ans

    def count_kmp(self, s):
        size = len(s)
        max_match_len = [0] * (size + 1)
        max_match_len[0] = -1
        l, r = -1, 0
        while r < size:
            if l == -1 or s[l] == s[r]:
                l += 1
                r += 1
                max_match_len[r] = l
            else:
                l = max_match_len[l]
        return max_match_len


if __name__ == "__main__":
    print(Solution().findGoodStrings(n=2, s1="aa", s2="da", evil="b"))  # 51
    print(Solution().findGoodStrings(n=8, s1="leetcode", s2="leetgoes", evil="leet"))  # 0
    print(Solution().findGoodStrings(n=2, s1="gx", s2="gz", evil="x"))  # 2
